package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/15 9:14
 */
public class C213 {

    // https://leetcode-cn.com/problems/house-robber-ii/
    // 暴力解: 从左往右偷
    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        return process(nums, 0, true);
    }

    private int process(int[] nums, int i, boolean canLast) {
        if (i >= nums.length) {
            return 0;
        }
        if (i == nums.length - 1) {
            return canLast ? nums[i] : 0;
        }
        int p1 = nums[i] + process(nums, i + 2, canLast && i != 0);
        int p2 = process(nums, i + 1, canLast);
        return Math.max(p1, p2);
    }


    // 范围区间偷
    public int rob2(int[] nums) {
        if (nums.length == 0)
            return 0;
        else if (nums.length == 1)
            return nums[0];
        else if (nums.length == 2)
            return Math.max(nums[0], nums[1]);
        else
            return Math.max(process2(nums, 0, nums.length - 2), process2(nums, 1, nums.length - 1));
    }

    private int process2(int[] nums, int start, int end) {
        int first = nums[start], second = Math.max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }


    // for test
    public static void main(String[] args) {
        C213 test = new C213();
        int[] nums = {200, 3, 140, 20, 10};
//        int[] nums = {1, 2, 1, 1};
//        int[] nums = {1, 3, 1, 3, 100};
//        int[] nums = {2,3,2};
//        int[] nums = {1,2,3,1};
//        int[] nums = {};
        System.out.println(test.rob(nums));
        System.out.println(test.rob2(nums));
    }

}
